package 两个字符串的删除操作;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/19 11:27
 * @description:
 * 给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
 * 示例：
 * 输入: "sea", "eat"
 * 输出: 2
 * 解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
 */
public class Solution {
    public int minDistance(String word1, String word2) {
        // 最长公共子序列
        // ① dp数组及其下标含义：dp[i][j]表示 word1 中以 i-1 结尾的字串，word2中以 j-1 结尾的字串，最长的公共子序列长度
        // ② 状态转移方程：如果当前字符相等 dp[i][j] = dp[i-1][j-1] + 1 else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        // ③ dp数组的初始化：dp[0][j] = 0; dp[i][0] = 0; 表示一方为空串的时，公共子序列长度为0
        // ④ 遍历顺序：从左上角到右下角
        // ⑤ 举例推导dp数组：word1 = "leetcode", word2 = "etco"
        //          index:      0   1   2   3   4   5   6   7   8


        int word1Len = word1.length();
        int word2Len = word2.length();

        int[][] dp = new int[word1Len + 1][word2Len + 1];
        int result = 0;

        for (int i = 1; i <= word1Len; i++) {
            for (int j = 1; j <= word2Len; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
                result = Math.max(result, dp[i][j]);
            }

            System.out.println(Arrays.toString(dp[i]));
        }

        return word1Len + word2Len - 2 * result;
    }
}
